//
//  ViewController.m
//  十大经典算法
//
//  Created by 亚古历险记 on 2020/3/15.
//  Copyright © 2020 iOS总结Demo. All rights reserved.
//
//  特别感谢 https://www.cnblogs.com/onepixel/p/7674659.html
#import "ViewController.h"

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    
    
    NSInteger count = 100;
    NSMutableSet * mutableSet = [NSMutableSet setWithCapacity:count];
    /// 1.1 循环100次
    for (NSInteger i = 0; i < count; i++) {
        NSInteger value = arc4random()%100;
        /// 1.2 把随机数添加到MutableSet里，NSMutableSet是不重复添加相同的值的
        [mutableSet addObject:[NSNumber numberWithInteger:value]];
    }
    /// 1.3 把随机数放到一个可变数组里
    NSMutableArray * array = [[NSMutableArray alloc] initWithArray:mutableSet.allObjects];
    
    /// 冒泡排序
//    [self action1:array];
    
    /// 选择排序
//    [self action2:array];
    
    /// 插入排序
//    [self action3:array];
    
    /// 希尔排序
    [self action4:array];
}


/**
冒泡排序: 时间复杂度O(n)~O(n2)
    1、比较相邻的元素。如果第一个比第二个大，就交换它们两个。
    2、对每一对相邻元素做同样的工作，从开始第一对到最后一对，这样在最后的元素应该就是最大的数
    3、针对所有的元素重复以上的步骤，除了最后一个；
    4、重复步骤1～3，直到排序完成
 */
- (void)action1:(NSMutableArray *)array {

    /// 1. 如果数组小于2，就不用继续排序了
    if (array.count < 2) {
        return;
    }
    
    /// 核心代码
    for (NSInteger i = 0; i < array.count; i ++) {
        
        for (NSInteger j = 0; j < array.count - i - 1; j ++) {
            /// 2 相邻元素做比较，如果前一个比后一个大，就互换位置
            if ([[array objectAtIndex:j] integerValue] > [[array objectAtIndex:j+1] integerValue]) {
                
                [array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
            }
        }
    }
    NSLog(@"%@",array);
}

/**
 选择排序：时间复杂度O(n)~O(n2)
    首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
 
 n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

    1、初始状态：无序区为R[1..n]，有序区为空；
    2、第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
    3、n-1趟结束，数组有序化了
 */
- (void)action2:(NSMutableArray *)array {
    NSInteger length = array.count;
    NSInteger minIndex;
    
    for (NSInteger i = 0; i < length - 1; i++) {
        minIndex = i;
        for (NSInteger j = i + 1; j < length; j++) {
            /// 寻找最小的数
            if ([[array objectAtIndex:j] integerValue] < [[array objectAtIndex:minIndex] integerValue]) {
                minIndex = j;
            }
        }
        [array exchangeObjectAtIndex:i withObjectAtIndex:minIndex];
    }
}

/**
    插入排序：时间复杂度O(n)~O(n2)
        工作原理是通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置插入
 
     1、从第一个元素开始，该元素被认为已经被排序
     2、取出下一个元素，在已经排序的序列中从后向前扫描
     3、如果该元素大于新元素，将该元素移到下一个位置
     4、重复上一步骤，直到找到已排序的元素小于或者等于新元素的位置
     5、最后一个元素的排序完毕即结束
 */
- (void)action3:(NSMutableArray *)array {
    
    for (NSInteger i = 1; i < array.count; i++) {
        for (NSInteger j = i; j > 0; j--) {
            
            if ([[array objectAtIndex:j] integerValue] < [[array objectAtIndex:j - 1] integerValue]) {
                [array exchangeObjectAtIndex:j withObjectAtIndex:j - 1];
            }
        }
    }
    NSLog(@"%@",array);
}


/**
    希尔排序：时间复杂度O(n)~O(n2)  平均 O(n1.3)
     第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
 
 */
- (void)action4:(NSMutableArray *)array {
    
    int count = (int)array.count;
    //初始增量为数组长度的一半，然后每次除以2取整
    for (int increment = count/2; increment>0; increment /=2) {
    //初始下标设为第一个增量的位置，然后递增
      for (int i = increment; i<count; i++) {
          //获取当前位置
          int j = i;
          //然后将此位置之前的元素，按照增量进行跳跃式比较
          while (j-increment>=0 && array[j]<array[j-increment]) {
              [array exchangeObjectAtIndex:j withObjectAtIndex:j-increment];
              j-=increment;
          }
      }
    }
    
    NSLog(@"%@",array);
}

- (void)action5:(NSMutableArray *)array {
    
}

- (void)action6:(NSMutableArray *)array {
    
}

- (void)action7:(NSMutableArray *)array {
    
}

- (void)action8:(NSMutableArray *)array {
    
}

- (void)action9:(NSMutableArray *)array {
    
}

- (void)action10:(NSMutableArray *)array {
    
}
@end
